home *** CD-ROM | disk | FTP | other *** search
/ AOL File Library: 2,801 to 2,900 / aol-file-protocol-4400-2801-to-2900.zip / AOLDLs / C++ Files Library / Graphic Gems I, II & III (C_C++) / Graphics Gems C Code.sea / GemsIII / bounding_volumes.c < prev    next >
Text File  |  1992-06-16  |  13KB  |  395 lines
  1.  
  2. #include <math.h>
  3.  
  4.  
  5. /****************************************************************************
  6. These definitions of vectors and matrices are used throughout this code.
  7. The constant M_PI_2 is equal to PI/2, or 1.57079632679489661923.
  8. ****************************************************************************/
  9.  
  10. typedef float    vec3[3];
  11. typedef float    mat4[4][4];
  12.  
  13.  
  14.  
  15. /****************************************************************************
  16. Transforms an object space point into world coordinates using the provided
  17. cumulative transformation matrix.
  18. ****************************************************************************/
  19.  
  20. transform_point(world, local, ctm)
  21. vec3 world;            /* returned world space point */
  22. vec3 local;            /* provided local space point */
  23. mat4 ctm;            /* cumulative transformation matrix */
  24. {
  25.    world[0] = local[0] * ctm[0][0] + local[1] * ctm[1][0] +
  26.           local[2] * ctm[2][0] + ctm[3][0];
  27.    world[1] = local[0] * ctm[0][1] + local[1] * ctm[1][1] +
  28.           local[2] * ctm[2][1] + ctm[3][1];
  29.    world[2] = local[0] * ctm[0][2] + local[1] * ctm[1][2] +
  30.           local[2] * ctm[2][2] + ctm[3][2];
  31. }
  32.  
  33.  
  34.  
  35. /****************************************************************************
  36. The provided point is compared against the current minimum and maximum
  37. values in X, Y, and Z.  If a new maximum or minimum is found, the
  38. min and max variables are updated.
  39. ****************************************************************************/
  40.  
  41. update_min_and_max(min, max, point)
  42. vec3 min, max;            /* provided extent that is to be modified */
  43. vec3 point;            /* world space point to be tested */
  44. {
  45.    int    i;
  46.  
  47.    for (i=0; i<3; i++) {
  48.       if (point[0] < min[0]) min[0] = point[0];
  49.       if (point[0] > max[0]) max[0] = point[0];
  50.       if (point[1] < min[1]) min[1] = point[1];
  51.       if (point[1] > max[1]) max[1] = point[1];
  52.       if (point[2] < min[2]) min[2] = point[2];
  53.       if (point[2] > max[2]) max[2] = point[2];
  54.    }
  55. }
  56.  
  57.  
  58.  
  59. /****************************************************************************
  60. The bounding volume of a cube is found.  Each of the cube's eight vertices
  61. is transformed into world space, and then compared to the current minimum
  62. and maximum values, which are updated if a new extremum is found.  The
  63. canonical cube is centered about the origin, with faces at X=-1, X=1, Y=-1,
  64. Y=1, Z=-1, and Z=1.
  65. ****************************************************************************/
  66.  
  67. cube_volume(min, max, ctm)
  68. vec3 min, max;            /* returned minimum and maximum of extent */
  69. mat4 ctm;            /* cumulative transformation */
  70. {
  71.    int         i;
  72.    vec3        point;
  73.    static vec3 corners[8] = {
  74.       -1, -1, -1,    1, -1, -1,    -1,  1, -1,    1,  1, -1,
  75.       -1, -1,  1,    1, -1,  1,    -1,  1,  1,    1,  1,  1
  76.    };
  77.  
  78.    min[0] = min[1] = min[2] = MAXFLOAT;
  79.    max[0] = max[1] = max[2] = -MAXFLOAT;
  80.  
  81.    for (i=0; i<8; i++) {
  82.       transform_point(point, corners[i], ctm);
  83.       update_min_and_max(min, max, point);
  84.    }
  85. }
  86.  
  87.  
  88.  
  89. /****************************************************************************
  90. The bounding volume of a collection of polygons is found.  The verts variable
  91. is a list of the vertices of the polygon collection, and the vertices need
  92. not be unique.  The num variable specifies how many vertices are in the list.
  93. Each vertex is transformed into world space, and then compared to the current
  94. miminum and maximum values, which are updated if a new extremum is found.
  95. ****************************************************************************/
  96.  
  97. polygons_volume(min, max, ctm, verts, num)
  98. vec3 min, max;            /* returned minimum and maximum of extent */
  99. mat4 ctm;            /* cumulative transformation */
  100. vec3 verts[];            /* list of vertices from polygons */
  101. int  num;            /* number of vertices in list */
  102. {
  103.    int  i;
  104.    vec3 point;
  105.  
  106.    min[0] = min[1] = min[2] = MAXFLOAT;
  107.    max[0] = max[1] = max[2] = -MAXFLOAT;
  108.  
  109.    for (i=0; i<num; i++) {
  110.       transform_point(point, verts[i], ctm);
  111.       update_min_and_max(min, max, point);
  112.    }
  113. }
  114.  
  115.  
  116.  
  117. /****************************************************************************
  118. Performs a safe arctangent calculation for the two provided numbers.  If the
  119. denominator is 0.o, atan2 is not called (it results in a floating exception
  120. on some machines).  Instead, + or - PI/2 is returned.
  121. ****************************************************************************/
  122.  
  123. float
  124. arctangent(a, b)
  125. float a, b;            /* operands for tan'(a/b) */
  126. {
  127.  
  128.    if (b != 0.0)
  129.       return atan2(a, b);
  130.    else if (a > 0.0)
  131.       return M_PI_2;
  132.    else
  133.       return -M_PI_2;
  134. }
  135.  
  136.  
  137.  
  138. /****************************************************************************
  139. The bounding volume of a cylinder is found.  The algorithm operates in
  140. three passes, one for each dimension.  In each pass the extrema of the
  141. bottom circle of the cylinder are found as values of the parameter t.
  142. These values are then used to calculate the position of the two points
  143. in the current dimension.  Finally, these points from the bottom circle
  144. and corresponding points from the top circle are considered while computing
  145. the minimum and maximum values of the current dimension.  The canonical
  146. cylinder has a radius of 1.0 from the Y axis, and ranges from Z=-1 to Z=1.
  147. ****************************************************************************/
  148.  
  149. cylinder_volume(min, max, ctm)
  150. vec3 min, max;            /* returned minimum and maximum of extent */
  151. mat4 ctm;            /* cumulative transformation matrix */
  152. {
  153.    int   i;
  154.    float t1, t2, p1, p2, tmp;
  155.  
  156.    for (i=0; i<3; i++) {
  157.  
  158.       /* calculate first extremum.  second is +/- PI on other side of circle */
  159.       t1 = arctangent(ctm[2][i], ctm[0][i]);
  160.       if (t1 <= 0)
  161.      t2 = t1 + M_PI;
  162.       else
  163.      t2 = t1 - M_PI;
  164.  
  165.       /* find and sort extrema locations in this dimension */
  166.       p1 = ctm[0][i]*cos(t1) - ctm[1][i] + ctm[2][i]*sin(t1) + ctm[3][i];
  167.       p2 = ctm[0][i]*cos(t2) - ctm[1][i] + ctm[2][i]*sin(t2) + ctm[3][i];
  168.       if (p1 > p2) {
  169.      tmp = p1;
  170.      p1 = p2;
  171.      p2 = tmp;
  172.       }
  173.  
  174.       /* add the difference between bottom and top circles to an extremum */
  175.       if (ctm[1][i] < 0) {
  176.      min[i] = p1 + 2 * ctm[1][i];
  177.      max[i] = p2;
  178.       }
  179.       else {
  180.      min[i] = p1;
  181.      max[i] = p2 + 2 * ctm[1][i];
  182.       }
  183.    }
  184. }
  185.  
  186.  
  187.  
  188. /****************************************************************************
  189. The bounding volume of a cone is found.  The algorithm checks the cone's
  190. bottom in three passes, one for each dimension.  In each pass the extrema
  191. of the circle are found as values of the parameter t.  These values are
  192. then used to calculate the position of the two points in the current dimension.
  193. Finally, these points are considered along with the transformed apex of the
  194. cone to compute the minimum and maximum extents.  The canonical cone has
  195. a base of radius 1.0 at Z=-1 and an apex at the point 0,1,0.
  196. ****************************************************************************/
  197.  
  198. cone_volume(min, max, ctm)
  199. vec3 min, max;            /* returned minimum and maximum of extent */
  200. mat4 ctm;            /* cumulative transformation matrix */
  201. {
  202.    int          i;
  203.    float        t1, t2, tmp;
  204.    vec3         point;
  205.    static vec3  apex = { 0, 1, 0 };
  206.  
  207.    for (i=0; i<3; i++) {
  208.  
  209.       /* calculate first extremum.  second is +/- PI on other side of circle */
  210.       t1 = arctangent(ctm[2][i], ctm[0][i]);
  211.       if (t1 <= 0)
  212.      t2 = t1 + M_PI;
  213.       else
  214.      t2 = t1 - M_PI;
  215.  
  216.       /* find and sort extrema locations in this dimension */
  217.       min[i] = ctm[0][i]*cos(t1) - ctm[1][i] + ctm[2][i]*sin(t1) + ctm[3][i];
  218.       max[i] = ctm[0][i]*cos(t2) - ctm[1][i] + ctm[2][i]*sin(t2) + ctm[3][i];
  219.       if (min[i] > max[i]) {
  220.      tmp = max[i];
  221.      max[i] = min[i];
  222.      min[i] = tmp;
  223.       }
  224.    }
  225.  
  226.    /* transform and check apex of cone */
  227.    transform_point(point, apex, ctm);
  228.    update_min_and_max(min, max, point);
  229. }
  230.  
  231.  
  232.  
  233. /****************************************************************************
  234. The bounding volume of a conic is found.  The algorithm checks the conic's
  235. bottom and top in three passes, one for each dimension.  In each pass the
  236. extrema of the circles are found as values of the parameter t.  These values
  237. are then used to calculate the position of the four points in the current
  238. dimension.  The conic has a base of radius 1.0 at Z=-1 and a top in the Y=1
  239. plane with a radius r around the Y axis.
  240. ****************************************************************************/
  241.  
  242. conic_volume(min, max, ctm, r)
  243. vec3  min, max;            /* returned minimum and maximum of extent */
  244. mat4  ctm;            /* cumulative transformation matrix */
  245. float r;            /* radius of top of conic */
  246. {
  247.    int   i;
  248.    float t1, t2, p1, p2, tmp;
  249.  
  250.    for (i=0; i<3; i++) {
  251.  
  252.       /* calculate first extremum.  second is +/- PI on other side of circle */
  253.       t1 = arctangent(ctm[2][i], ctm[0][i]);
  254.       if (t1 <= 0)
  255.      t2 = t1 + M_PI;
  256.       else
  257.      t2 = t1 - M_PI;
  258.  
  259.       /* find and sort bottom extrema locations in this dimension */
  260.       p1 = ctm[0][i]*cos(t1) - ctm[1][i] + ctm[2][i]*sin(t1) + ctm[3][i];
  261.       p2 = ctm[0][i]*cos(t2) - ctm[1][i] + ctm[2][i]*sin(t2) + ctm[3][i];
  262.       if (p1 < p2) {
  263.      min[i] = p1;
  264.      max[i] = p2;
  265.       }
  266.       else {
  267.      min[i] = p2;
  268.      max[i] = p1;
  269.       }
  270.  
  271.       /* find, sort and compare top extrema locations in this dimension */
  272.       p1 = r*ctm[0][i]*cos(t1) + ctm[1][i] + r*ctm[2][i]*sin(t1) + ctm[3][i];
  273.       p2 = r*ctm[0][i]*cos(t2) + ctm[1][i] + r*ctm[2][i]*sin(t2) + ctm[3][i];
  274.       if (p1 < p2) {
  275.      if (p1 < min[i])
  276.         min[i] = p1;
  277.      if (p2 > max[i])
  278.         max[i] = p2;
  279.       }
  280.       else {
  281.      if (p2 < min[i])
  282.         min[i] = p2;
  283.      if (p1 > max[i])
  284.         max[i] = p1;
  285.       }
  286.    }
  287. }
  288.  
  289.  
  290.  
  291. /****************************************************************************
  292. The bounding volume of a sphere is found.  The algorithm performs three
  293. passes, one for each dimension.  In each pass the extrema of the surface
  294. are found as values of the parameters u and v.  These values are then used
  295. to calculate the position of the two points in the current dimension.
  296. Finally, these points are sorted to find the minimum and maximum extents.
  297. The canonical sphere has a radius of 1.0 and is centered at the origin.
  298. ****************************************************************************/
  299.  
  300. sphere_volume(min, max, ctm)
  301. vec3 min, max;            /* returned minimum and maximum of extent */
  302. mat4 ctm;            /* cumulative transformation matrix */
  303. {
  304.    int   i;
  305.    float u1, u2, v1, v2, tmp, denominator;
  306.  
  307.    for (i=0; i<3; i++) {
  308.  
  309.       /* calculate first extremum. */
  310.       u1 = arctangent(ctm[2][i], ctm[0][i]);
  311.       denominator = ctm[0][i]*cos(u1) + ctm[2][i]*sin(u1);
  312.       v1 = arctangent(ctm[1][i], denominator);
  313.  
  314.       /* second extremum is +/- PI from u1, negative of v1 */
  315.       if (u1 <= 0)
  316.      u2 = u1 + M_PI;
  317.       else
  318.      u2 = u1 - M_PI;
  319.       v2 = -v1;
  320.  
  321.       /* find and sort extrema locations in this dimension */
  322.       min[i] =
  323.      ctm[0][i] * cos(u1) * cos(v1) +
  324.      ctm[1][i] * sin(v1) +
  325.      ctm[2][i] * sin(u1) * cos(v1) +
  326.      ctm[3][i];
  327.       max[i] =
  328.      ctm[0][i] * cos(u2) * cos(v2) +
  329.      ctm[1][i] * sin(v2) +
  330.      ctm[2][i] * sin(u2) * cos(v2) +
  331.      ctm[3][i];
  332.       if (min[i] > max[i]) {
  333.      tmp = max[i];
  334.      max[i] = min[i];
  335.      min[i] = tmp;
  336.       }
  337.    }
  338. }
  339.  
  340.  
  341.  
  342. /****************************************************************************
  343. The bounding volume of a torus is found.  The algorithm performs three
  344. passes, one for each dimension.  In each pass the extrema of the surface
  345. are found as values of the parameters u and v.  These values are then used
  346. to calculate the position of the two points in the current dimension.
  347. Finally, these points are sorted to find the minimum and maximum extents.
  348. The torus is defined as the rotation of a circle that is perpendicular to
  349. the XZ plane.  This circle has radius q, and its center lies in the XZ
  350. plane and is rotated about the Y axis in a circle of radius r.  The value
  351. of q must be less than that of r.
  352. ****************************************************************************/
  353.  
  354. torus_volume(min, max, ctm, r, q)
  355. vec3  min, max;            /* returned minimum and maximum of extent */
  356. mat4  ctm;            /* cumulative transformation matrix */
  357. float r;            /* major radius of torus */
  358. float q;            /* minor radius of torus */
  359. {
  360.    int   i;
  361.    float u1, u2, v1, v2, tmp, denominator;
  362.  
  363.    for (i=0; i<3; i++) {
  364.  
  365.       /* calculate first extremum.  assure that -PI/2 <= v1 <= PI/2 */
  366.       u1 = arctangent(ctm[2][i], ctm[0][i]);
  367.       denominator = ctm[0][i]*cos(u1) + ctm[2][i]*sin(u1);
  368.       v1 = arctangent(ctm[1][i], denominator);
  369.  
  370.       /* second extremum is +/- PI from u1, negative of v1 */
  371.       if (u1 <= 0)
  372.      u2 = u1 + M_PI;
  373.       else
  374.      u2 = u1 - M_PI;
  375.       v2 = -v1;
  376.  
  377.       /* find and sort extrema locations in this dimension */
  378.       min[i] =
  379.      ctm[0][i] * cos(u1) * (r + q * cos(v1)) +
  380.      ctm[1][i] * sin(v1) * q +
  381.      ctm[2][i] * sin(u1) * (r + q * cos(v1)) +
  382.      ctm[3][i];
  383.       max[i] =
  384.      ctm[0][i] * cos(u2) * (r + q * cos(v2)) +
  385.      ctm[1][i] * sin(v2) * q +
  386.      ctm[2][i] * sin(u2) * (r + q * cos(v2)) +
  387.      ctm[3][i];
  388.       if (min[i] > max[i]) {
  389.      tmp = max[i];
  390.      max[i] = min[i];
  391.      min[i] = tmp;
  392.       }
  393.    }
  394. }
  395.